# coding: utf-8


class OrderDemo:
    def order_bucket(self, nums):
        # 设置桶大小
        max_num = max(nums)
        # 设置桶的序列
        bucket_nums = [0] * (max_num + 1)
        # 统计每个数字出现的次数
        for num in nums:
            bucket_nums[num] += 1
        bucket_len = len(bucket_nums)
        # 设置排序后的序列
        sorted_nums = []
        # 排序，找出非0的位置，将当前值插入序列
        for bucket_num in range(bucket_len):
            if bucket_nums[bucket_num] != 0:
                bucket_sub_len = bucket_nums[bucket_num]
                for index in range(bucket_sub_len):
                    sorted_nums.append(bucket_num)
        return sorted_nums

    def fibo(self, num):
        nums = [0, 1]
        # num >= 2时，对数组进行操作
        for i in range(num - 2):
            nums.append(nums[i] + nums[i + 1])
        return nums[num - 1]

    def order_bubble(self, nums):
        # 设置排序次数
        order_time = len(nums) - 1
        flag = 1
        for index in range(order_time, 0, -1):
            if flag:
                flag = 0
                # 设置每次排序的比较次数
                for j in range(index):
                    if nums[j] > nums[j + 1]:
                        nums[j], nums[j + 1] = nums[j + 1], nums[j]
                        flag = 1
            else:
                # 数列已经有序
                break
        return nums

    def find_pos(self, lists, low, high):
        key = lists[low]
        while low < high:
            while low < high and lists[high] >= key:
                high -= 1
            lists[low] = lists[high]
            while low < high and lists[low] <= key:
                low += 1
            lists[high] = lists[low]
        lists[low] = key
        return low

    def order_quick(self, alist, first, last):
        if first < last:
            # 找到每次排序结束的节点位置
            split_pos = self.find_pos(alist, first, last)
            # 节点左边有序排列
            self.order_quick(alist, first, split_pos - 1)
            # 节点右边有序排列
            self.order_quick(alist, split_pos + 1, last)

    def _test_order_insert(self):
        """
        od = OrderDemo()
        od._test_order_insert()
        """
        # 有序列表排序
        list1 = [10, 20, 30, 40, 50]
        num = int(input('插入的数字: '))
        list1.append(num)
        cnt = len(list1)
        print(cnt)
        for i in range(cnt):
            # 找到插入的位置
            if num < list1[i]:
                for j in range(cnt, i, -1):
                    list1[j - 1] = list1[j - 2]
                list1[i] = num
                break
        print(list1)

    def _test_order_bucket(self):
        """
        od = OrderDemo()
        od._test_order_bucket()
        """
        # 桶排序
        list2 = [10, 20, 15, 13, 30, 40, 50]
        print(self.order_bucket(list2))

    def _test_order_fibonacci_cycle(self):
        """
        od = OrderDemo()
        od._test_order_fibonacci_cycle()
        """
        # 斐波那契数列, 非递归
        print(self.fibo(10))

    def _test_order_bubble(self):
        """
        od = OrderDemo()
        od._test_order_bubble()
        """
        # 冒泡排序
        l = [10, 30, 20, 40, 25]
        print(self.order_bubble(l))

    def _test_order_quick(self):
        """
        od = OrderDemo()
        od._test_order_quick()
        """
        # 快速排序, 分成两个部分，小数在左边，大数在右边
        lists = [11, 15, 20, 4, 2, 50, 66, 1]
        self.order_quick(lists, 0, len(lists) - 1)
        print(lists)


if __name__ == '__main__':
    od = OrderDemo()
    od._test_order_quick()
